package sort.leetcode_75_medium_partition;

public class SortColors {
    /**
     * 数组中只有三个数组：0,1,2 将数组分成 左边是0 中间是1 右边是2 （就是排序）
     *
     * @param nums 给定待分区的数组
     *             <p>
     *             最直接的解法：1. 使用排序算法  2. 使用Arrays.sort()
     *             <p>
     *             但是这两种方法都不是最优解，根据题目的要求：
     *             1.你可以不使用代码库中的排序函数来解决这道题吗？
     *             2.你能想出一个仅使用常数空间的一趟扫描算法吗？
     *             <p>
     *             使用一趟扫描算法和常数级别的空间的方法是这道题最优解。
     *             <p>
     *             利用快速排序的partition思想，由于数组只存在0，1，2三个数组
     *             可以利用双指针循环遍历的方法，
     *             使用p1从左至右扫描，使用p2从右至左扫描，如果p2遇到0就放到p1处，p1遇到2就放p2处，放置的同时递增指针的位置。
     */
    public void sortColors(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int N = nums.length;
        //双指针
        int p1 = 0, p2 = N - 1;
        for (int i = 0; i <= p2; i++) {
            /*
                为什么要使用while而不是if，因为交换后的i值不确定， 具体看例子
                    比如数组：2, 1, 0, 2;
                            p1       p2
                            i
                    交换后的结果还是：2, 1, 0, 2，只不过p2减小1
                                   p1    p2
                                   i
                    此时交换后的i还是2，所以还需要交换，如果使用if的话，i会递增（那么i就到1元素处）
                    继续交换：0, 1, 2, 2
                               p1
                               p2
                               i
             */
            while (i <= p2 && nums[i] == 2) {
                swap(nums, i, p2);
                p2--;
            }
            if (nums[i] == 0) {
                swap(nums, i, p1);
                p1++;
            }
        }
    }
    /*
        更清晰更容易理解的版本
     */
    public void sortColors2(int[] nums){
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        //同样的双指针
        int left = 0;
        int right = len - 1;
        // [0...left) == 0;
        // [left...i) == 1;
        // (right...len - 1] == 2;
        int i = 0;
        while(i <= right){
            if(nums[i] == 0){
                swap(nums, i, left);
                left++;
                i++;
            }else if(nums[i] == 1){
                i++;
            }else {
                //交换后值是不确定的，所以不能递增i
                swap(nums, i, right);
                right--;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
